#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <sys/time.h>

void qsort3(int *x, int l, int u) {
    int t, i, j;
    int tmp;

    if (l >= u)  return;

    t = x[l];
    i = l;
    j = u+1;

    for(;;) {
        do { ++i; } while ( i <= u && x[i] < t );

        do { --j; } while ( x[j] > t );

        if (i > j) break;

        tmp = x[i]; x[i] = x[j]; x[j] = tmp;
    }
    tmp = x[l]; x[l] = x[j]; x[j] = tmp;

    qsort3(x, l, j-1);
    qsort3(x, j+1, u);
}

int cutoff = 10;
void qsort4(int *x, int l, int u) {
    int t, i, j;
    int pos;
    int tmp;

    if (u <= l + 4)  return;

    pos = l + (int)( (double)rand() / RAND_MAX * (u-l) );

    tmp = x[l]; x[l] = x[pos]; x[pos] = tmp;

    t = x[l];
    i = l;
    j = u+1;

    for(;;) {
        do { ++i; } while ( i <= u && x[i] < t );

        do { --j; } while ( x[j] > t );

        if (i > j) break;

        tmp = x[i]; x[i] = x[j]; x[j] = tmp;
    }
    tmp = x[l]; x[l] = x[j]; x[j] = tmp;

    qsort4(x, l, j-1);
    qsort4(x, j+1, u);
}

int fcomp(const void *a, const void *b)
{
    return *(int *)a - *(int *)b;
}

#define MAXNUM 1024*1024*1024
#define NUM 1024 * 1024

int main(int argc, char *argv[])
{
    int i;

    char *fun = "qsort4";
    char *data = "rand";

    int *x = NULL;

    struct timeval ts, te;
    struct timezone tz;

    if (argc > 2) data = argv[2];
    if (argc > 1) fun = argv[1];

    if ( 0 == strcmp(data, "rand") )srand((int)time(0));

    x = malloc(sizeof(int) * NUM);
    for(i=0; i<NUM; ++i) {
        if ( 0 == strcmp(data, "rand") )
            x[i] = (int)((double)rand() / RAND_MAX * MAXNUM);
        else
            x[i] = i;
    }

    printf("Starting sort %d numbers ...\n", NUM);
    gettimeofday(&ts, &tz);

    if ( 0 == strcmp(fun, "qsort3") )
        qsort3(x, 0, NUM-1);
    else if ( 0 == strcmp(fun, "qsort0") )
        qsort(x, NUM, sizeof(int), fcomp);
    else
        qsort4(x, 0, NUM-1);

    gettimeofday(&te, &tz);

    printf("Finish sort...\n");
    printf("Time elapsed: %.6f s\n", 
           te.tv_sec - ts.tv_sec + 
           (te.tv_usec - ts.tv_usec) * 0.000001);

/*
    for(i=0; i<NUM; ++i) {
        printf("%d: %d\n", i, x[i]);
    }
*/
    free(x);
}
